package leetcode;

/**
 * 寻找两个有序数组的中位数
 *
 * @author zhangj
 * @date 2019/12/13
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * <p>
 */
public class LT04 {
	public static void main(String[] args) {
		int[] nums1 = new int[]{1};
		int[] nums2 = new int[]{3, 4};
		System.out.println(findMedianSortedArrays2(nums1, nums2));
	}

	public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
		int length1 = nums1.length;
		int length2 = nums2.length;
		int lengthall = length1 + length2;
		int[] all = new int[lengthall];
		int i = 0, j = 0, k = 0;
		while (i < length1 && j < length2) {
			if (nums1[i] < nums2[j]) {
				all[k] = nums1[i];
				i++;
			} else {
				all[k] = nums2[j];
				j++;
			}
			k++;
		}
		while (i < length1) {
			all[k] = nums1[i];
			i++;
			k++;
		}
		while (j < length2) {
			all[k] = nums2[j];
			j++;
			k++;
		}

		double result;
		if (lengthall % 2 == 0) {
			result = (all[lengthall / 2 - 1] + all[lengthall / 2]) * 1.0 / 2;
		} else {
			result = all[lengthall / 2];
		}
		return result;
	}

	public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
		int m = nums1.length;
		int n = nums2.length;
		boolean even = true;
		int time;

		if ((m + n) % 2 == 0) {
			time = (m + n) / 2;
		} else {
			time = (m + n - 1) / 2;
			even = false;
		}

		if (m == 0) {
			if (even) {
				return ((nums2[time] + nums2[time - 1]) * 1.0) / 2;
			} else {
				return nums2[time];
			}
		}

		if (n == 0) {
			if (even) {
				return ((nums1[time] + nums1[time - 1]) * 1.0) / 2;
			} else {
				return nums1[time];
			}
		}

		int a = 0;
		int b = 0;
		int[] result = new int[2];
		for (int i = 0; i < time; i++) {
			if (a >= nums1.length) {
				b++;
				result[i % 2] = nums2[b - 1];
			} else if (b >= nums2.length) {
				a++;
				result[i % 2] = nums1[a - 1];
			} else {
				if (nums1[a] < nums2[b]) {
					a++;
					result[i % 2] = nums1[a - 1];
				} else if (nums1[a] > nums2[b]) {
					b++;
					result[i % 2] = nums2[b - 1];
				} else {
					if ((a + 1) >= nums1.length) {
						b++;
						result[i % 2] = nums2[b - 1];
					} else {
						a++;
						result[i % 2] = nums1[a - 1];
					}
				}
			}
		}

		if (even) {
			return (result[0] + result[1]) * 1.0 / 2;
		} else {
			return result[time / 2];
		}
	}
}
